#include <bits/stdc++.h>
#include <climits>
#include <unordered_map>
using namespace std;

class Solution {
public:
    bool check(unordered_map<char, int>& cnt){
        for(auto& it: cnt){
            if(it.second < 0) return false;
        }
        return true;
    }
    string minWindow(string s, string t) {
        if(s.size() < t.size()) return "";
        unordered_map<char, int> cnt;
        int left, right; left = 0; right = t.size();
        int ans_left, ans_right; ans_left = 0; ans_right = 0;
        int ans_len = INT_MAX;
        int n = s.size();
        for(auto& chr : t) --cnt[chr];
        
        for(int i=0; i<t.size(); ++i) ++cnt[s[i]];
        while(left<=n-t.size() && right<=s.size()){
            if(check(cnt)==true){
                if(right - left < ans_len){
                    ans_left = left;
                    ans_right = right;
                    ans_len = ans_right - ans_left;
                }
                --cnt[s[left]];
                ++left;
            } 
            else {
                ++cnt[s[right]];
                ++right;
            }
        }
        return s.substr(ans_left, ans_right-ans_left);
    }
};

int main(){

}